class Solution(object):
    def probabilityOfHeads(self, prob, target):
        """
        :type prob: List[float]
        :type target: int
        :rtype: float
        """
        n = len(prob)
        DP = [[0 for _ in range(n)] for _ in range(target + 1)]
        DP[0][0] = 1 - prob[0]
        for j in range(1, n):
            DP[0][j] = (1 - prob[j]) * DP[0][j - 1]

        for i in range(1, target + 1):
            for j in range(i - 1, n):
                if j == i - 1:
                    if j == 0:
                        DP[i][j] = prob[j]
                    else:
                        DP[i][j] = prob[j] * DP[i - 1][j - 1]
                else:
                    DP[i][j] = prob[j] * DP[i - 1][j - 1] + (1 - prob[j]) * DP[i][j - 1]
        return DP[-1][-1]


data = Solution()
prob = [0.5, 0.5, 0.5, 0.5]
target = 4
print(data.probabilityOfHeads(prob, target))

